The question is, what is the solution here? It can't really be a path, right, through the

state space, because you only control half of the path. Right? You move your pawn, the

opponent moves some other piece, you move your rook, your opponent moves some other piece.

You can't follow a plan. So what we need instead is a strategy for max or a strategy for min,

which tells you what to do, no matter what your opponent does. Okay? For every state,

whether you're in it or not, you have to know how to make the next move. If you contrast

that with, say, single agent search in Romania, you never have to know what to do. If you

have a solution, it never tells you what to do when you're in Xerent, because you know

in my solution I'm never going to go to Xerent or Oradea or whatever, right? But here it

could be that your opponent somehow teleports you to Oradea, right? And then you have to

know what to do. So a strategy is something that's a much, much, much, much, much bigger

object than a solution. But it's the best we can kind of do. And if we have this notion

of strategies, which is a function for max or min from all the states to actions, right?

So which prepares you for all possibilities, then we can ask ourselves what would optimality

be here? And you could actually look at all the strategies. There are many of them, of

course, because there are many, many, many, many, many of these functions, and these functions

are terribly big. An optimal strategy is the one that always gets you the best result.

Which is terrible to find, yes.

Well, in chess, how do we know what is a good solution?

A good strategy?

Yeah, if we only go one step, it's not like I win or I lose. I could maybe schlagen one

of these players.

If you have a strategy, you can look at all possible games that conform to the strategy.

You can look at all the games where you follow the strategy and the opponent does whatever

they like.

Isn't that too much to compute?

Oh yeah, absolutely. In most cases. We have strategies for tic-tac-toe. We have strategies

for cala 4 to 6, I think, but not beyond. They're big. You can download them, but it

takes you a while. This is a theoretical construct, let's say, for chess and Go and so on. But

we need to wrap our minds around what we would like to have. And that's what I'm trying to

tease out here.

Okay?

Yep.

But it's true. Not only the strategies are too big, but they're also too many to do anything.

So we can only do theory. And sometimes practice for games that are trivial. Okay?

So what I said what you would really want is an optimal strategy is that no matter what

your opponent does, you optimize against that. You can make things a little bit better by

assuming that you have a strategy that works when your opponent behaves optimally. I'm

not going to formalize that because that's kind of mutually recursive and therefore difficult.

So we leave it out. But it can be defined. But we're not doing it. We're not going to

do anything with these things anyway because they are just too big.

How big? Well, reachable states in chess is something like a 40-digit number. So well

beyond the billion nodes threshold. Even worse in Go. But then we want to remember that we're

not actually doing state spaces, which are complicated beasts, graphs typically. But

we're doing game trees. And they get bigger because they have repeated states. Apparently

lots of repeated states. Okay? And maybe even unreachable states and so on. Okay? And if

you get paler in the face at that number, this number should actually shock you. And

Go has been estimated to have search trees of that size. Which was why almost all AI

researchers said Go? No way. Right? Go is something like 540 times as bad as chess.

Okay? Boy, were we wrong. AI lives after all. Okay? So strategies, difficult. That also